#define  _CRT_SECURE_NO_WARNINGS
class Solution {
    void mergeSort(vector<int>& arr, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) >> 1;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        int i = left, j = mid + 1, cur = left;
        // for(int b1 = left, b2 = mid + 1; b1 <= mid && b2 <= right;)
        // {
        //     if((long long)arr[b1] > (long long)arr[b2] * 2) 
        //     {
        //         ret += right - b2 + 1;
        //         b1++;
        //     }
        //     else b2++;
        // }
        // while(i <= mid && j <= right)
        //     if(arr[i] > arr[j]) tmp[cur++] = arr[i++];
        //     else tmp[cur++] = arr[j++];
        // while(i <= mid) tmp[cur++] = arr[i++];
        // while(j <= right) tmp[cur++] = arr[j++];
        // for(int i = left; i <= right; i++) arr[i] = tmp[i];
        for (int b1 = left, b2 = mid + 1; b1 <= mid && b2 <= right;)
        {
            if (arr[b1] / 2.0 > arr[b2])
            {
                ret += mid - b1 + 1;
                b2++;
            }
            else b1++;
        }
        while (i <= mid && j <= right)
            tmp[cur++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        while (i <= mid) tmp[cur++] = arr[i++];
        while (j <= right) tmp[cur++] = arr[j++];
        for (int i = left; i <= right; i++) arr[i] = tmp[i];
    }
    vector<int> tmp;
    int ret;
public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return ret;
    }
};